package arithmetic;

import org.junit.jupiter.api.Test;

import java.text.MessageFormat;

/**
 * 查找并打印 10000以内的素数 （质数）
 * @author jiangfeng 2019/7/11 21:46
 */
public class FindPrimeNum {

    @Test
    public void test(){
        int num =100000000;
        long startTime = System.currentTimeMillis();
        //findPrimeNum(num);
        findPrimeNum3(num);

        System.out.println("耗时:"+(System.currentTimeMillis()-startTime));
    }


    /**
     * 10万
     * 素数个数:9,591
     * 耗时:2082
     */
    public static void findPrimeNum(int num){
        long count=0;
        for (int i = 3; i < num+1; i=i+2) {// 直接跳过偶数
            boolean flag = true;
            for(int j=2;j<i/2;j++){
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            if(flag){
               // System.out.println(i);
                count++;
            }
        }
        System.out.println(MessageFormat.format("素数个数:{0}",count));
    }


    /**
     * 方法2 筛选法:思路 2，的倍数全去掉，依次向上増，剩下的就是素数
     * https://blog.csdn.net/lingling_1/article/details/44462185
     */
    public static void findPrimeNum2(int num){
        // 初始化数组
        int[] a = new int[num];
        for (int i = 0; i < num - 1; i++) {
            a[i] = i + 1;
        }
    }

    /**
     * 10万
     * 素数个数:9,591
     * 234 (加上根号后 18)
     * @param num
     * 一亿
     * 素数个数:50,847,533
     * 耗时:43777 （加根号后 耗时:2251）
     *
     *
     */
    public static void findPrimeNum3(int num) {
        // 初始化数组
        boolean[] a = new boolean[num]; // 以boolean数组表示数，默认都为false ， 定义下标+1为其代表的数，素数设为false，不是素数为ture
        a[0] = true;
        a[1] = true;// 1,2是特殊值，先置为非素数
        int n = 2;
        while (true) {
            for (int j = 2; j * n <= num; j++) { //j倍数， n 当前的最小质数。
                a[j * n - 1] = true;
            }
            n = findNextPrinme(n, a, num);
            // if (n==0|| n > Math.sqrt(num))
            if (n > Math.sqrt(num)) {
                break;
            }
        }
        int count = 0;
        for (int i = 0; i < num - 1; i++) {
            if (!a[i]) {
                //System.out.println(i+1);
                count++;
            }
        }
        System.out.println(MessageFormat.format("素数个数:{0}", count));
    }

    /**
     * 给出素数n， 找到n的下一个素数
     * @param n
     * @return
     */
    public static int findNextPrinme(int n, boolean[] a,int num) {
        int i = n + 1;
        /*if (i > num - 1) {//避免数组越界
            return 0; // 似乎不用判断也行，但是加上也没影响多少性能
        }*/
        while (a[i-1]) {
            i++;
        }
        return i;
    }

}
